
/**
 * @method 冒泡排序
 * @desc 时间复杂度：最好O(n)，最差O(n^2)
 * @param {array} arr 要排序的数组
 */
const bubbleSort = arr => {

  if(!Array.isArray(arr) || arr.length <= 1) return arr;

  const newArr = [...arr];
  const length = newArr.length;
  for(let i = 0; i < length - 1; i++) {
    for(let j = 0; j < length - 1- i; j++) {
      if(newArr[j] > newArr[j + 1]) {
        [newArr[j], newArr[j + 1]] = [newArr[j + 1], newArr[j]];
      }
    }
  }

  return newArr;
}

/**
 * @method 快速排序
 * @desc 时间复杂度：O(N*logN)
 * @param {array} arr 
 */
const quickSort = arr => {

  if(!Array.isArray(arr) || arr.length <= 1) return arr;

  // const newArr = [...arr];
  // const length = newArr.length;

  const sort = (arr2, idx1, idx2) => {
    const pivotIndex = Math.floor(arr2.length / 2);// 找基准索引
    const pivot = arr2.splice(pivotIndex, 1)[0];
    const left = [], right = [];
    for(let i = 0, length = arr2.length; i < length; i++) {
      if(arr2[i] <pivot) {
        left.push(arr2[i]);
      } else {
        right.push(arr2[i]);
      }
    }

    return quickSort(left).concat([pivot], quickSort(right));
  }

  return sort(arr);

}

const arr = [99,343,5,2,44,56,12,-2,-90];

console.log(quickSort(arr), arr)

console.log(Math.floor(2.3))

export {
  bubbleSort, quickSort
}